package features.advance.leetcode.string.easy;

import java.util.*;

/**
 *  面试题 01.02. 判定是否互为字符重排
 *
 *  难度：简单
 *
 * 给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，
 * 能否变成另一个字符串。
 *
 * 示例 1：
 *
 * 输入: s1 = "abc", s2 = "bca"
 * 输出: true
 * 示例 2：
 *
 * 输入: s1 = "abc", s2 = "bad"
 * 输出: false
 * 说明：
 *
 * 0 <= len(s1) <= 100
 * 0 <= len(s2) <= 100
 *
 * @author LIN
 * @date 2021-09-16
 */
public class Interview01_02 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public boolean CheckPermutation(String s1, String s2) {
                // 将字符串转换成字符数组
                char[] s1Chars = s1.toCharArray();
                char[] s2Chars = s2.toCharArray();
                // 对字符数组进行排序
                Arrays.sort(s1Chars);
                Arrays.sort(s2Chars);
                // 再将字符数组转换成字符串，比较是否相等
                return new String(s1Chars).equals(new String(s2Chars));
            }
        };
        solution = new Solution(){

            @Override
            public boolean CheckPermutation(String s1, String s2) {
                if (s1.length() != s2.length()) {
                    return false;
                }
                char[] s1Chars = s1.toCharArray();
                // 同时解析两个字符串成记录字符出现次数的map格式的数据
                Map<Character, Integer> s1Map = getMap(s1);
                Map<Character, Integer> s2Map = getMap(s2);
                for (char s1Char : s1Chars) {
                    if (!s2Map.containsKey(s1Char) || !s2Map.get(s1Char).equals(s1Map.get(s1Char))) {
                        return false;
                    }
                }
                return true;
            }

            // 统计指定字符串str中各字符的出现次数，并以Map的形式返回
            private Map<Character, Integer> getMap(String str) {
                Map<Character, Integer> map = new HashMap<>();
                char[] chars = str.toCharArray();
                for (char aChar : chars) {
                    map.put(aChar, map.getOrDefault(aChar, 0) + 1);
                }
                return map;
            }

        };
        String s1 = "a";
        String s2 = "ab";
        boolean res = solution.CheckPermutation(s1, s2);
        System.out.println(res);
    }

    static class Solution {

        public boolean CheckPermutation(String s1, String s2) {
            Map<Character, Integer> tmp = new HashMap<>(16);
            String t1 = s1.length() > s2.length()?s1:s2;
            String t2 = s1.length() > s2.length()?s2:s1;

            for (char c1 : t1.toCharArray()) {
               if(tmp.containsKey(c1)){
                   tmp.put(c1,tmp.get(c1)+1);
               }else{
                   tmp.put(c1,1);
               }
            }

            for (char c2 : t2.toCharArray()) {
                if(tmp.containsKey(c2)){
                    tmp.put(c2,tmp.get(c2)-1);
                    if(tmp.get(c2) == 0){
                        tmp.remove(c2);
                    }
                }

            }
            return tmp.isEmpty();
        }
    }
}
